#include <iostream>
using namespace std;
class Solution {
public:
    int mySqrt(int x) {

        if (x < 1) {
            return 0;
        }
        if (x < 4) {
            return 1;
        } else if (x<9) {
            return 2;
        }

        uint64_t i=x/2;
        uint64_t j=i;
        while(x < i*i) {
            j = i;
            i = i/2;
        }

        if (x == i*i) {
            return i;
        }

        while(i<j) {
            if (x<=i*i) {
                break;
            }
            i++;
        }
        if (x==i*i) {
            return i;
        } else {
            return i-1;
        }
    }
};

int main() {
    Solution s;
    for (int i=1; i<257; i++)
        cout << i << "\t" << s.mySqrt(i) << endl;
}
